package Leetcode.LeetcodeDemo1;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class LeetCode940 {
    public static HashSet<List<Character>> hashSet=new HashSet<>();
    public static int distinctSubseqII(String s) {
        char[] charArr=s.toCharArray();
        return progress(charArr,0,new ArrayList<Character>())-1;
    }
    public static int progress(char[] arr, int n, List<Character> list){
        if(n==arr.length){
            if(hashSet.contains(list)){
                return 0;
            }else{
                hashSet.add(list);
                return 1;
            }
        }
        int sum=0;
        List<Character> resKeep=new ArrayList<>(list);
        List<Character> noKeep=new ArrayList<>(list);
        resKeep.add(arr[n]);
        sum+=progress(arr,n+1,resKeep)+progress(arr,n+1,noKeep);
        return sum;
    }
    public static void main(String[] args){
        String s="-pcrdhwdxmqdznbenhwjsenjhvulyve";
        System.out.println(distinctSubseqII(s));
    }
}
